<!DOCTYPE html><html><head>
<title>math::numtheory - Tcl Math Library</title>
<style type="text/css"><!--
    HTML {
	background: 	#FFFFFF;
	color: 		black;
    }
    BODY {
	background: 	#FFFFFF;
	color:	 	black;
    }
    DIV.doctools {
	margin-left:	10%;
	margin-right:	10%;
    }
    DIV.doctools H1,DIV.doctools H2 {
	margin-left:	-5%;
    }
    H1, H2, H3, H4 {
	margin-top: 	1em;
	font-family:	sans-serif;
	font-size:	large;
	color:		#005A9C;
	background: 	transparent;
	text-align:		left;
    }
    H1.doctools_title {
	text-align: center;
    }
    UL,OL {
	margin-right: 0em;
	margin-top: 3pt;
	margin-bottom: 3pt;
    }
    UL LI {
	list-style: disc;
    }
    OL LI {
	list-style: decimal;
    }
    DT {
	padding-top: 	1ex;
    }
    UL.doctools_toc,UL.doctools_toc UL, UL.doctools_toc UL UL {
	font:		normal 12pt/14pt sans-serif;
	list-style:	none;
    }
    LI.doctools_section, LI.doctools_subsection {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding: 	0em;
    }
    PRE {
	display: 	block;
	font-family:	monospace;
	white-space:	pre;
	margin:		0%;
	padding-top:	0.5ex;
	padding-bottom:	0.5ex;
	padding-left:	1ex;
	padding-right:	1ex;
	width:		100%;
    }
    PRE.doctools_example {
	color: 		black;
	background: 	#f5dcb3;
	border:		1px solid black;
    }
    UL.doctools_requirements LI, UL.doctools_syntax LI {
	list-style: 	none;
	margin-left: 	0em;
	text-indent:	0em;
	padding:	0em;
    }
    DIV.doctools_synopsis {
	color: 		black;
	background: 	#80ffff;
	border:		1px solid black;
	font-family:	serif;
	margin-top: 	1em;
	margin-bottom: 	1em;
    }
    UL.doctools_syntax {
	margin-top: 	1em;
	border-top:	1px solid black;
    }
    UL.doctools_requirements {
	margin-bottom: 	1em;
	border-bottom:	1px solid black;
    }
--></style>
</head>
<!-- Generated from file 'numtheory.man' by tcllib/doctools with format 'html'
   -->
<!-- Copyright &amp;copy; 2010 Lars Hellstr&amp;ouml;m &amp;lt;Lars dot Hellstrom at residenset dot net&amp;gt;
   -->
<!-- math::numtheory.n
   -->
<body><hr> [
   <a href="../../../../../../../../home">Tcllib Home</a>
&#124; <a href="../../../../toc.html">Main Table Of Contents</a>
&#124; <a href="../../../toc.html">Table Of Contents</a>
&#124; <a href="../../../../index.html">Keyword Index</a>
&#124; <a href="../../../../toc0.html">Categories</a>
&#124; <a href="../../../../toc1.html">Modules</a>
&#124; <a href="../../../../toc2.html">Applications</a>
 ] <hr>
<div class="doctools">
<h1 class="doctools_title">math::numtheory(n) 1.1.1 tcllib &quot;Tcl Math Library&quot;</h1>
<div id="name" class="doctools_section"><h2><a name="name">Name</a></h2>
<p>math::numtheory - Number Theory</p>
</div>
<div id="toc" class="doctools_section"><h2><a name="toc">Table Of Contents</a></h2>
<ul class="doctools_toc">
<li class="doctools_section"><a href="#toc">Table Of Contents</a></li>
<li class="doctools_section"><a href="#synopsis">Synopsis</a></li>
<li class="doctools_section"><a href="#section1">Description</a></li>
<li class="doctools_section"><a href="#section2">Bugs, Ideas, Feedback</a></li>
<li class="doctools_section"><a href="#keywords">Keywords</a></li>
<li class="doctools_section"><a href="#category">Category</a></li>
<li class="doctools_section"><a href="#copyright">Copyright</a></li>
</ul>
</div>
<div id="synopsis" class="doctools_section"><h2><a name="synopsis">Synopsis</a></h2>
<div class="doctools_synopsis">
<ul class="doctools_requirements">
<li>package require <b class="pkgname">Tcl <span class="opt">?8.5?</span></b></li>
<li>package require <b class="pkgname">math::numtheory <span class="opt">?1.1.1?</span></b></li>
</ul>
<ul class="doctools_syntax">
<li><a href="#1"><b class="cmd">math::numtheory::isprime</b> <i class="arg">N</i> <span class="opt">?<i class="arg">option</i> <i class="arg">value</i> ...?</span></a></li>
<li><a href="#2"><b class="cmd">math::numtheory::firstNprimes</b> <i class="arg">N</i></a></li>
<li><a href="#3"><b class="cmd">math::numtheory::primesLowerThan</b> <i class="arg">N</i></a></li>
<li><a href="#4"><b class="cmd">math::numtheory::primeFactors</b> <i class="arg">N</i></a></li>
<li><a href="#5"><b class="cmd">math::numtheory::primesLowerThan</b> <i class="arg">N</i></a></li>
<li><a href="#6"><b class="cmd">math::numtheory::primeFactors</b> <i class="arg">N</i></a></li>
<li><a href="#7"><b class="cmd">math::numtheory::uniquePrimeFactors</b> <i class="arg">N</i></a></li>
<li><a href="#8"><b class="cmd">math::numtheory::factors</b> <i class="arg">N</i></a></li>
<li><a href="#9"><b class="cmd">math::numtheory::totient</b> <i class="arg">N</i></a></li>
<li><a href="#10"><b class="cmd">math::numtheory::moebius</b> <i class="arg">N</i></a></li>
<li><a href="#11"><b class="cmd">math::numtheory::legendre</b> <i class="arg">a</i> <i class="arg">p</i></a></li>
<li><a href="#12"><b class="cmd">math::numtheory::jacobi</b> <i class="arg">a</i> <i class="arg">b</i></a></li>
<li><a href="#13"><b class="cmd">math::numtheory::gcd</b> <i class="arg">m</i> <i class="arg">n</i></a></li>
<li><a href="#14"><b class="cmd">math::numtheory::lcm</b> <i class="arg">m</i> <i class="arg">n</i></a></li>
<li><a href="#15"><b class="cmd">math::numtheory::numberPrimesGauss</b> <i class="arg">N</i></a></li>
<li><a href="#16"><b class="cmd">math::numtheory::numberPrimesLegendre</b> <i class="arg">N</i></a></li>
<li><a href="#17"><b class="cmd">math::numtheory::numberPrimesLegendreModified</b> <i class="arg">N</i></a></li>
<li><a href="#18"><b class="cmd">math::numtheory::differenceNumberPrimesLegendreModified</b> <i class="arg">lower</i> <i class="arg">upper</i></a></li>
</ul>
</div>
</div>
<div id="section1" class="doctools_section"><h2><a name="section1">Description</a></h2>
<p>This package is for collecting various number-theoretic operations, with
a slight bias to prime numbers.</p>
<dl class="doctools_definitions">
<dt><a name="1"><b class="cmd">math::numtheory::isprime</b> <i class="arg">N</i> <span class="opt">?<i class="arg">option</i> <i class="arg">value</i> ...?</span></a></dt>
<dd><p>The <b class="cmd">isprime</b> command tests whether the integer <i class="arg">N</i> is a
  prime, returning a boolean true value for prime <i class="arg">N</i> and a
  boolean false value for non-prime <i class="arg">N</i>. The formal definition of
  'prime' used is the conventional, that the number being tested is
  greater than 1 and only has trivial divisors.</p>
<p>To be precise, the return value is one of <b class="const">0</b> (if <i class="arg">N</i> is
  definitely not a prime), <b class="const">1</b> (if <i class="arg">N</i> is definitely a
  prime), and <b class="const">on</b> (if <i class="arg">N</i> is probably prime); the latter
  two are both boolean true values. The case that an integer may be
  classified as &quot;probably prime&quot; arises because the Miller-Rabin
  algorithm used in the test implementation is basically probabilistic,
  and may if we are unlucky fail to detect that a number is in fact
  composite. Options may be used to select the risk of such
  &quot;false positives&quot; in the test. <b class="const">1</b> is returned for &quot;small&quot;
  <i class="arg">N</i> (which currently means <i class="arg">N</i> &lt; 118670087467), where it is
  known that no false positives are possible.</p>
<p>The only option currently defined is:</p>
<dl class="doctools_options">
  
<dt><b class="option">-randommr</b> <i class="arg">repetitions</i></dt>
<dd><p>which controls how many times the Miller-Rabin test should be
    repeated with randomly chosen bases. Each repetition reduces the
    probability of a false positive by a factor at least 4. The
    default for <i class="arg">repetitions</i> is 4.</p></dd>
</dl>
<p>Unknown options are silently ignored.</p></dd>
<dt><a name="2"><b class="cmd">math::numtheory::firstNprimes</b> <i class="arg">N</i></a></dt>
<dd><p>Return the first N primes</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number of primes to return</p></dd>
</dl></dd>
<dt><a name="3"><b class="cmd">math::numtheory::primesLowerThan</b> <i class="arg">N</i></a></dt>
<dd><p>Return the prime numbers lower/equal to N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Maximum number to consider</p></dd>
</dl></dd>
<dt><a name="4"><b class="cmd">math::numtheory::primeFactors</b> <i class="arg">N</i></a></dt>
<dd><p>Return a list of the prime numbers in the number N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number to be factorised</p></dd>
</dl></dd>
<dt><a name="5"><b class="cmd">math::numtheory::primesLowerThan</b> <i class="arg">N</i></a></dt>
<dd><p>Return the prime numbers lower/equal to N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Maximum number to consider</p></dd>
</dl></dd>
<dt><a name="6"><b class="cmd">math::numtheory::primeFactors</b> <i class="arg">N</i></a></dt>
<dd><p>Return a list of the prime numbers in the number N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number to be factorised</p></dd>
</dl></dd>
<dt><a name="7"><b class="cmd">math::numtheory::uniquePrimeFactors</b> <i class="arg">N</i></a></dt>
<dd><p>Return a list of the <em>unique</em> prime numbers in the number N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number to be factorised</p></dd>
</dl></dd>
<dt><a name="8"><b class="cmd">math::numtheory::factors</b> <i class="arg">N</i></a></dt>
<dd><p>Return a list of all <em>unique</em> factors in the number N, including 1 and N itself</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number to be factorised</p></dd>
</dl></dd>
<dt><a name="9"><b class="cmd">math::numtheory::totient</b> <i class="arg">N</i></a></dt>
<dd><p>Evaluate the Euler totient function for the number N (number of numbers
relatively prime to N)</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number in question</p></dd>
</dl></dd>
<dt><a name="10"><b class="cmd">math::numtheory::moebius</b> <i class="arg">N</i></a></dt>
<dd><p>Evaluate the Moebius function for the number N</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number in question</p></dd>
</dl></dd>
<dt><a name="11"><b class="cmd">math::numtheory::legendre</b> <i class="arg">a</i> <i class="arg">p</i></a></dt>
<dd><p>Evaluate the Legendre symbol (a/p)</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">a</i> (in)</dt>
<dd><p>Upper number in the symbol</p></dd>
<dt>integer <i class="arg">p</i> (in)</dt>
<dd><p>Lower number in the symbol (must be non-zero)</p></dd>
</dl></dd>
<dt><a name="12"><b class="cmd">math::numtheory::jacobi</b> <i class="arg">a</i> <i class="arg">b</i></a></dt>
<dd><p>Evaluate the Jacobi symbol (a/b)</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">a</i> (in)</dt>
<dd><p>Upper number in the symbol</p></dd>
<dt>integer <i class="arg">b</i> (in)</dt>
<dd><p>Lower number in the symbol (must be odd)</p></dd>
</dl></dd>
<dt><a name="13"><b class="cmd">math::numtheory::gcd</b> <i class="arg">m</i> <i class="arg">n</i></a></dt>
<dd><p>Return the greatest common divisor of <i class="term">m</i> and <i class="term">n</i></p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">m</i> (in)</dt>
<dd><p>First number</p></dd>
<dt>integer <i class="arg">n</i> (in)</dt>
<dd><p>Second number</p></dd>
</dl></dd>
<dt><a name="14"><b class="cmd">math::numtheory::lcm</b> <i class="arg">m</i> <i class="arg">n</i></a></dt>
<dd><p>Return the lowest common multiple of <i class="term">m</i> and <i class="term">n</i></p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">m</i> (in)</dt>
<dd><p>First number</p></dd>
<dt>integer <i class="arg">n</i> (in)</dt>
<dd><p>Second number</p></dd>
</dl></dd>
<dt><a name="15"><b class="cmd">math::numtheory::numberPrimesGauss</b> <i class="arg">N</i></a></dt>
<dd><p>Estimate the number of primes according the formula by Gauss.</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number in question, should be larger than 0</p></dd>
</dl></dd>
<dt><a name="16"><b class="cmd">math::numtheory::numberPrimesLegendre</b> <i class="arg">N</i></a></dt>
<dd><p>Estimate the number of primes according the formula by Legendre.</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number in question, should be larger than 0</p></dd>
</dl></dd>
<dt><a name="17"><b class="cmd">math::numtheory::numberPrimesLegendreModified</b> <i class="arg">N</i></a></dt>
<dd><p>Estimate the number of primes according the modified formula by Legendre.</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">N</i> (in)</dt>
<dd><p>Number in question, should be larger than 0</p></dd>
</dl></dd>
<dt><a name="18"><b class="cmd">math::numtheory::differenceNumberPrimesLegendreModified</b> <i class="arg">lower</i> <i class="arg">upper</i></a></dt>
<dd><p>Estimate the number of primes between tow limits according the modified formula by Legendre.</p>
<dl class="doctools_arguments">
<dt>integer <i class="arg">lower</i> (in)</dt>
<dd><p>Lower limit for the primes, should be larger than 0</p></dd>
<dt>integer <i class="arg">upper</i> (in)</dt>
<dd><p>Upper limit for the primes, should be larger than 0</p></dd>
</dl></dd>
</dl>
</div>
<div id="section2" class="doctools_section"><h2><a name="section2">Bugs, Ideas, Feedback</a></h2>
<p>This document, and the package it describes, will undoubtedly contain
bugs and other problems.
Please report such in the category <em>math :: numtheory</em> of the
<a href="http://core.tcl.tk/tcllib/reportlist">Tcllib Trackers</a>.
Please also report any ideas for enhancements you may have for either
package and/or documentation.</p>
<p>When proposing code changes, please provide <em>unified diffs</em>,
i.e the output of <b class="const">diff -u</b>.</p>
<p>Note further that <em>attachments</em> are strongly preferred over
inlined patches. Attachments can be made by going to the <b class="const">Edit</b>
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar.</p>
</div>
<div id="keywords" class="doctools_section"><h2><a name="keywords">Keywords</a></h2>
<p><a href="../../../../index.html#number_theory">number theory</a>, <a href="../../../../index.html#prime">prime</a></p>
</div>
<div id="category" class="doctools_section"><h2><a name="category">Category</a></h2>
<p>Mathematics</p>
</div>
<div id="copyright" class="doctools_section"><h2><a name="copyright">Copyright</a></h2>
<p>Copyright &copy; 2010 Lars Hellstr&ouml;m &lt;Lars dot Hellstrom at residenset dot net&gt;</p>
</div>
</div></body></html>
